package simple;

import jdk.nashorn.internal.runtime.regexp.joni.MatcherFactory;
import jdk.nashorn.internal.runtime.regexp.joni.Regex;
import sun.misc.Regexp;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/11/29 23:14
 */
public class No392_判断子序列 {
    public static void main(String[] args) {
        Solution392 solution392 = new Solution392();
        String s = "abdz";
        String t = "acbzdz";
        boolean subsequence = solution392.isSubsequence(s, t);
        System.out.println(subsequence);
    }
}

class Solution392 {
    public boolean isSubsequence(String s, String t) {
        //一次遍历
        int red = 0;
        int green = 0;
        while (red<s.length() && green < t.length()) {//只做绿指针
            if (s.charAt(red) == t.charAt(green)) {
                red++;
            }
            green++;
        }
        return red == s.length();
    }
}



    //public boolean isSubsequence(String s, String t) {
    //    //动态规划
    //    int hang = t.length() + 1; //7行
    //    int lie = 26;
    //    int[][] dp = new int[hang][lie];
    //    //最后?行初始化
    //    for (int i = 0; i < 26; i++) {
    //        dp[hang - 1][i] = hang - 1;
    //    }
    //
    //    //开始填充其他行
    //    for (int i = t.length() - 1; i >= 0; i--) {
    //        for (int j = 0; j < 26; j++) {
    //            if (t.charAt(i) - 'a' == j) {
    //                dp[i][j] = i;
    //            } else {
    //                dp[i][j] = dp[i + 1][j];
    //            }
    //        }
    //    }
    //    //使用dp进行匹配 abdz
    //    int h = 0;
    //    for (int i = 0; i < s.length(); i++) {
    //        //迭代找的位置
    //        h = dp[h][s.charAt(i) - 'a'];
    //        if (h == t.length()) {
    //            //在遍历过程中发现溢出下标
    //            return false;
    //        }
    //        //+1,防止重复dp[0][0] ....
    //        h++;
    //    }
    //    return true;
    //}



    //public boolean isSubsequence(String s, String t) {
    //    if ("".equals(s)) {
    //        return true;
    //    }
    //    //abc
    //    //xxxxaxxxxbxxxcxxx
    //
    //    //栈
    //    Stack<Character> stack = new Stack<>();
    //    //初始化栈
    //    for (char ss : s.toCharArray()) {
    //        stack.push(ss);
    //    }
    //
    //    //倒序遍历t
    //    for (int i = t.length() - 1; i >= 0; i--) {
    //        //拿出s形成的栈顶元素
    //        char check = stack.peek();
    //        if (t.charAt(i) == check) {
    //            stack.pop();
    //        }
    //        //栈为空,后面不要继续运行了
    //        if (stack.isEmpty()) {
    //            return true;
    //        }
    //    }
    //
    //    //遍历完成,没有找到和栈顶元素一样
    //    return stack.isEmpty();
    //
    //}